package cz.cvut.fit.mi.par.b101.mgc;

import cz.cvut.fit.mi.par.b101.mgc.stack.Stack;

/**
 * Hlavní třída programu.
 *
 * @author masekji4@fit.cvut.cz
 */
public class Main {

    private static Stack stack;

    /**
     * Hlavní metoda programu.
     *
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // Pole vstupních hodnot.
        //int[][] points = {{1, 1}, {4, 2}, {6, 3}, {8, 4}, {10, 5}, {12, 6}};
        //int[][] points = {{1, 1}, {8, 4}, {5, 3}, {1, 3}, {3, 2}, {5, 1}};
        int[][] points = {{3, 2}, {4, 5}, {1, 4}, {7, 3}, {2, 6}, {7, 7}, {5, 1}, {3, 8}};

        // V C++ by bylo vhodnější nahradit množinou, pokud ji má, aby se
        // při každé expanzi nemuselo procházet celé pole k zjištění, které body
        // je možné použít.
        boolean[] map = new boolean[points.length];

        // Nejkratší nalezená cesta
        int[] path = new int[points.length];

        // Délka nejkratší nalezené cesty
        int shortest = Integer.MAX_VALUE;

        // Zásobník
        stack = new Stack();

        // Aktuálně expandovaný uzel cesty.
        Node pred = null;

        do {
            // Uzel naposledy přidaný do zásobníku.
            Node last = null;

            // Expanze uzlu.
            for (int i= 0; i < map.length; i++) {
                // Nebyl-li uzel ještě expandován...
                if (!map[i]) {
                    Node node = new Node(i, pred == null ? 0 : pred.getLevel() + 1,
                                    pred,
                                    // Výpočet délky úsečky
                                    pred == null ? 0 : pred.getLength() +
                                    // Přičtení nového úseku
                                    (int)Math.round(
                                        Math.sqrt(
                                            Math.pow(Math.abs(points[i][0] - points[pred.getPoint()][0]), 2)
                                          + Math.pow(Math.abs(points[i][1] - points[pred.getPoint()][1]), 2)
                                        ) * 100
                                    )
                               );

                    // Přesahuje-li v tomto uzlu délka cesty délku doposud
                    // nalezené nejkratší cesty, není uzel přidán do zásobníku.
                    if (node.getLength() < shortest) {
                        last = node;

                        stack.push(last);
                    }
                }
            }

            // Nastavení uzlu, jenž bude expandován v dalším cyklu.
            // Byla-li délka ve všech uzlech delší než délka doposud nejkratší
            // nalezené cesty, bude expandovaný uzel odstraněn ze zásobníku,
            // aby mohli být expandovány jiné trasy.
            if (last != null) {
                pred = last;
                map[pred.getPoint()] = true;
            }

            // Nezbývá již žádný volný bod nebo expandovaný uzel nemá žádná
            // následovníky, v nichž by délka nepřesahovala délku doposud
            // nejkratší nalezené cesty.
            if (pred.getLevel() == points.length - 1 || last == null) {

                Node node = stack.pop();
                map[node.getPoint()] = false;

                // Uložení posloupnosti v případě, že je kratší než dříve
                // nalezená.
                if (pred.getLength() < shortest && last != null) {

                    shortest = pred.getLength();
                    
                    int i = points.length - 1;

                    while (node != null) {
                        path[i] = node.getPoint();

                        node = node.getPred();

                        i--;
                    }
                }

                // Odstranění větve ze zásobníku, aby mohla být rozvinuta další
                
                node = stack.pop();

                while (pred.getLevel() != node.getLevel() && !stack.isEmpty()) {
                    map[node.getPoint()] = false;
                    pred = node;
                    node = stack.pop();
                }

                if (pred.getLevel() == node.getLevel()) {
                    pred = node;
                    stack.push(pred);
                    map[pred.getPoint()] = true;
                }
            }
            
        } while (!stack.isEmpty());


        // Výpis posloupnosti bodů, jimiž vede nejkratší cesta.

        for (int i= 0; i < path.length; i++) {
            System.out.print(path[i] + "-");
        }

        System.out.println(shortest);
    }

}
